/*
 * TracePath.c
 *   define the processes about PATH.
 *    1. make PATHs for a function.
 *    		tr_PathMake...
 *    2. make LOOPs for a function.
 *    		tr_PathLoop...
 *    3. trace function by PATH.
 *    		tr_Path...
 *  Created on: 2012/07/06
 *      Author: guanxiaoying
 */
#include "../tracedef.h"
#include "../../table/core_table.h"
#include "trace_cmd.h"
#ifdef DEBUG
#define trace_path_log printf
//#define trace_path_log(...)
#define trace_path_log2 printf
#else
#define trace_path_log(...)
#define trace_path_log2(...)
#endif

/* for making PATHs */
struct _TRPATHINFO{
	AST astCurrBeginNode;
	AST astBegin;
	U2  condition;
}stTrPathInfo;
/**
 * command list's feature
 *    0 in 0 out  dead node. It does not make sense.
 *    0 in 1 out  ASM_CMD_FUNCENTRY/ASM_CMD_CONFLUX( There are JUMP-NODE in all input-paths )
 *    0 in 2 out  ASM_CMD_BRANCH( There are JUMP-NODEs in the input-path )
 *    N in 0 out  ASM_CMD_FUNCEXIT
 *    N in 1 out  ASM_CMD_CONFLUX  /  ASM_CMD_CHOOSEEND
 *    N in N out  non-existent
 *    1 in 0 out  ASM_CMD_FUNCEXIT
 *    1 in 2 out  ASM_CMD_BRANCH( There is not JUMP-NODE in the input-path )/ ASM_CMD_CHOOSE
 *    1 in 1 out  Others
 */
/***********************************************
 * FUNCTIONS for MAKING PATHs
 ***********************************************/
/* set to the "pathOut" property of COMMAND-LIST which is the begin COMMAND */
static VOID tr_PathMakeAddToBeginNode( AST astCmdList, AST astNewPathInfo ){
	/*  astCmdList:  the begin node of astNewPathInfo  */
	/*  astNewPathInfo: a PATH-OUT path of astCmdList  */
	AST astPrePathInfo;
	AST astPathInfo;

	astPrePathInfo = 0;
	astPathInfo = stCmdListMetaAccess.pathOut.get( astCmdList );
	while( astPathInfo ){
		astPrePathInfo = astPathInfo;
		astPathInfo = stCmdPathInfoAccess.pathOut_next.get( astPathInfo );
	}
	if( astPrePathInfo == 0 ){
		/* the first OUT-PATH of "astCmdList" node */
		/* set OUT-PATH to node */
		stCmdListMetaAccess.pathOut.set( astCmdList, astNewPathInfo );
		/* set pathIn of new PATH if there is */
		astPrePathInfo = stCmdListMetaAccess.pathIn.get( astCmdList );
		stCmdPathInfoAccess.pathIn.set( astNewPathInfo, astPrePathInfo );
		/* set pathOut of every IN-PATH  */
		while( astPrePathInfo != 0 ){
			stCmdPathInfoAccess.pathOut.set( astPrePathInfo, astNewPathInfo );
			astPrePathInfo = stCmdPathInfoAccess.pathIn_next.get( astPrePathInfo );
		}
	}else{
		/* not the first OUT-PATH of "astCmdList" node */
		/* add to the end of  OUT-PATH chain  */
		stCmdPathInfoAccess.pathOut_next.set( astPrePathInfo, astNewPathInfo );
		/* set pathIn of new PATH if there is */
		astPrePathInfo = stCmdListMetaAccess.pathIn.get( astCmdList );
		stCmdPathInfoAccess.pathIn.set( astNewPathInfo, astPrePathInfo );
		/* for IN-PATH, only the first one of the OUT-PATH chain will be recorded.
		 * * so nothing to do  */
	}
}
/* set to the "pathIn" property of COMMAND-LIST which is the end COMMAND */
static VOID tr_PathMakeAddToEndNode( AST astExit ){
	/*  astExit:  the end COMMAND of a PATH  */
	AST astPrePathInfo;
	AST astBegin;
	AST astPathInfo;
	AST astCmdList = 0;

	if( stTrPathInfo.astCurrBeginNode > 0 ){
		/*  the begin command should not be none  */
		astPrePathInfo = 0;
		astPathInfo = stCmdListMetaAccess.pathIn.get( astExit );
		while( astPathInfo ){
			/* already added?  */
			astBegin = stCmdPathInfoAccess.beginNode.get( astPathInfo );
			if( astBegin == stTrPathInfo.astCurrBeginNode
				&& stCmdPathInfoAccess.condition.get( astPathInfo ) == stTrPathInfo.condition ){
				/* already added( astPathInfo != 0), nothing to do */
				break;
			}
			astPrePathInfo = astPathInfo;
			astPathInfo = stCmdPathInfoAccess.pathIn_next.get( astPathInfo );
		}
		if( astPathInfo == 0 ){
			/* create a new PATH */
			stCmdPathInfoAccess.alloc(1);
			astPathInfo = stCmdPathInfoAccess.getMax();
			if( stTrPathInfo.astBegin == 0 ){
				/* the entry PATH of a function */
				stTrPathInfo.astBegin = astPathInfo;
			}
			stCmdPathInfoAccess.beginNode.set( astPathInfo, stTrPathInfo.astCurrBeginNode  );
			stCmdPathInfoAccess.endNode.set( astPathInfo, astExit );
			stCmdPathInfoAccess.condition.set( astPathInfo, stTrPathInfo.condition );
			if( astPrePathInfo == 0 ){
				/* the first IN-PATH of astExit command */
				stCmdListMetaAccess.pathIn.set( astExit, astPathInfo );

				/* set pathOut of new PATH */
				astPrePathInfo = stCmdListMetaAccess.pathOut.get( astExit );
				stCmdPathInfoAccess.pathOut.set( astPathInfo, astPrePathInfo );
				/* set pathIn of every OUT-PATH */
				while( astPrePathInfo != 0 ){
					stCmdPathInfoAccess.pathIn.set( astPrePathInfo, astPathInfo );
					astPrePathInfo = stCmdPathInfoAccess.pathOut_next.get( astPrePathInfo );
				}
			}else{
				/* not the first IN-PATH of astExit node */
				stCmdPathInfoAccess.pathIn_next.set( astPrePathInfo, astPathInfo );
				/* set pathOut of new PATH if there is */
				astPrePathInfo = stCmdListMetaAccess.pathOut.get( astExit );
				stCmdPathInfoAccess.pathOut.set( astPathInfo, astPrePathInfo );
				/* for OUT-PATH, only the first one of the IN-PATH chain will be recorded,
				 * so nothing to do  */
			}
			/* add PATH to begin command */
			tr_PathMakeAddToBeginNode( stTrPathInfo.astCurrBeginNode, astPathInfo );
			/* set the new PATH to every command which is in the PATH */
			astCmdList = stTrPathInfo.astCurrBeginNode;
			while( astCmdList ){
				stCmdListMetaAccess.pathInfo.set( astCmdList, astPathInfo );
				if( astCmdList == astExit ){
					break;
				}
				astCmdList = TraceCmdGetNextByPath( astCmdList, astPathInfo );
			}
		}
		/* else : added PATH, nothing to do */
	}
	/* else: the begin command is none,
	 * it's not a normal case, so do not add a new PATH */
}

/* process of ASM_CMD_RETURN command, no OUT-PATH */
static S4 tr_PathMakeReturn( VOID ){
	S4 rc = TRACEEXIT_SUCCESS;
	AST astFunction = stCmdCurrTraceInfo.astFunction;
	AST astExit = LinkFunction.getFunctionExit( astFunction );

	if( stTrPathInfo.astCurrBeginNode > 0 ){
		/* the end command is ASM_CMD_FUNCEXIT. but not ASM_CMD_RETURN.
		 * because ASM_CMD_INC/ASM_CMD_DEC maybe exist after ASM_CMD_RETURN,
		 * but nothing exists after ASM_CMD_FUNCEXIT */
		tr_PathMakeAddToEndNode( astExit );
	}
	/* there is no PATH after returned. clear the begin command */
	stTrPathInfo.astCurrBeginNode = 0;
	stCmdCurrTraceInfo.astNext = 0;
	stCmdCurrTraceInfo.astTable = 0;
	return rc;
}
/* process of ASM_CMD_FUNCEXIT command. no OUT-PATH*/
static S4 tr_PathMakeExit( VOID ){
	S4 rc = TRACEEXIT_SUCCESS;
	AST astCmdList = stCmdCurrTraceInfo.astTable;
	if( stTrPathInfo.astCurrBeginNode > 0 ){
		tr_PathMakeAddToEndNode( astCmdList );
	}
	stTrPathInfo.astCurrBeginNode = 0;
	stCmdCurrTraceInfo.astNext = 0;
	stCmdCurrTraceInfo.astTable = 0;
	return rc;
}
/* process of ASM_CMD_CONFLUX command. multi-IN-PATH, one OUT-PATH */
static S4 tr_PathMakeConflux( VOID ){
	S4 rc = TRACEEXIT_SUCCESS;
	AST astExit = stCmdCurrTraceInfo.astTable;
	AST astCurr;
	AST astMaxCmdStack;
	AST astConflux;

	if( stTrPathInfo.astCurrBeginNode > 0 ){
		tr_PathMakeAddToEndNode( astExit );
	}
	stTrPathInfo.condition = PATH_TRUE;
	stTrPathInfo.astCurrBeginNode = astExit;

	/* For the efficiency of tracing algorithm,
	 *    n*2 but not n^2
	 * The trace stops at the end of a "for/while/do/switch/if" statement
	 * until all the statements in it are traced.
	 * Same to TRACE of COX.
	 *  */
	astMaxCmdStack = stCmdStackAccess.getMax();
	astCurr = stCmdStackAccess.currObject.get( astMaxCmdStack );
	/* not necessary to check the kind of top-stack
	 * because only branch-nodes could be pushed in this mode */
	astConflux = LinkCommandList.getNext( astCurr );
	if( astConflux == stCmdCurrTraceInfo.astTable ){
		/* The CONFLUX command of the latest BRANCH command(the top of stack).
		 * STOP!  */
		stCmdCurrTraceInfo.astNext = 0;
		stCmdCurrTraceInfo.astTable = 0;
	}else{
		/* continue */
		stCmdCurrTraceInfo.astTable = stCmdCurrTraceInfo.astNext;
		stCmdCurrTraceInfo.astNext = LinkCommandList.getNext( stCmdCurrTraceInfo.astTable );
	}
	return rc;
}
/* process of ASM_CMD_JUMP command. one IN-PATH, one OUT-PATH */
static S4 tr_PathMakeJump( VOID ){
	S4 rc = TRACEEXIT_SUCCESS;
	AST astOperand = LinkCommandList.getLeftOperand( stCmdCurrTraceInfo.astTable );
	AST astExit = LinkOperand.getParameter( astOperand );

	/* add the PATH which ends with ASM_CMD_JUMP command */
	tr_PathMakeAddToEndNode( stCmdCurrTraceInfo.astTable );
	stTrPathInfo.condition = PATH_TRUE;
	stTrPathInfo.astCurrBeginNode = stCmdCurrTraceInfo.astTable;
	/* add the PATH which begins with ASM_CMD_JUMP command,
	 * it will end with a ASM_CMD_CONFLUX command. */
	tr_PathMakeAddToEndNode( astExit );

	/* NOTICE: do not jump. */
	/* DO NOT make path from JUMP command to the next one */
	stTrPathInfo.astCurrBeginNode  = 0;
	stCmdCurrTraceInfo.astTable = stCmdCurrTraceInfo.astNext;
	stCmdCurrTraceInfo.astNext = LinkCommandList.getNext( stCmdCurrTraceInfo.astTable );
	return rc;
}
/* process of ASM_CMD_BRANCH command. one IN-PATH, multi(2) OUT-PATHs */
static S4 tr_PathMakeBranch( VOID ){
	S4 rc = TRACEEXIT_SUCCESS;
//	U2  times;
	AST astLeft;
	AST astOperand;
	AST astCurr;
	AST astMaxCmdStack;

	astMaxCmdStack = stCmdStackAccess.getMax();
	astCurr = stCmdStackAccess.currObject.get( astMaxCmdStack );
	if( stCmdCurrTraceInfo.pathFlag == PATH_TRUE ){
		/* the first time, for true path */
		if( astCurr != stCmdCurrTraceInfo.astTable ){
			/* it's not the top one of stack */

			/* 1. add a new PATH which ends with ASM_CMD_BRANCH command */
			tr_PathMakeAddToEndNode( stCmdCurrTraceInfo.astTable );
			/* first time: the path when the condition is true */
			stTrPathInfo.condition = PATH_TRUE;
			stTrPathInfo.astCurrBeginNode = stCmdCurrTraceInfo.astTable;

			/* push the false path to stack */
			stCmdCurrTraceInfo.pathFlag = PATH_FALSE;
			rc = Tr_StkCmdProcess( STACK_PUSH );
			astMaxCmdStack = stCmdStackAccess.getMax();
			/* first time to trace true-path */
			stCmdStackAccess.times.set( astMaxCmdStack, 1 );
			/* get the next command-list */
			astOperand = LinkCommandList.getLeftOperand( stCmdCurrTraceInfo.astTable );
			astLeft = LinkOperand.getParameter( astOperand );
			stCmdCurrTraceInfo.astTable = astLeft;
			stCmdCurrTraceInfo.astNext = LinkCommandList.getNext( astLeft );
			stCmdCurrTraceInfo.pathFlag = PATH_TRUE;
			/* For next BRANCH command  if there is any,
			 * trace from the true_path. */

		}else {
			/* second time, finish the trace */
			stCmdCurrTraceInfo.astNext = 0;
			stCmdCurrTraceInfo.astTable = 0;
			stCmdCurrTraceInfo.pathFlag = PATH_TRUE;
		}
	}else if ( stCmdCurrTraceInfo.pathFlag == PATH_FALSE ){
		/* false path */
		if( astCurr != stCmdCurrTraceInfo.astTable ){
			/* second time.
			 * The IN_PATH of this branch-node was added,
			 *  so do not call tr_PathMakeAddToEndNode */
			stTrPathInfo.condition = PATH_FALSE;
			stTrPathInfo.astCurrBeginNode = stCmdCurrTraceInfo.astTable;

			/* push the finish mark(PATH_NONE) to stack */
			stCmdCurrTraceInfo.pathFlag = PATH_NONE;
			rc = Tr_StkCmdProcess( STACK_PUSH );
			astMaxCmdStack = stCmdStackAccess.getMax();
			/* first time to trace false-path */
//			times = stCmdStackAccess.times.set( astMaxCmdStack, 1 );

			astOperand = LinkCommandList.getRightOperand( stCmdCurrTraceInfo.astTable );
			astLeft = LinkOperand.getParameter( astOperand );
			stCmdCurrTraceInfo.astTable = astLeft;
			stCmdCurrTraceInfo.astNext = LinkCommandList.getNext( astLeft );
			stCmdCurrTraceInfo.pathFlag = PATH_TRUE;
			/* For next BRANCH command  if there is any,
			 * trace from the true_path. */

		}else {
			/* second time, finish the trace */
			stCmdCurrTraceInfo.astNext = 0;
			stCmdCurrTraceInfo.astTable = 0;
			stCmdCurrTraceInfo.pathFlag = PATH_TRUE;
		}
	}else{
		/* the finish mark(PATH_NONE) */
		stTrPathInfo.astCurrBeginNode = 0;
		stTrPathInfo.condition = PATH_TRUE;
		astLeft = LinkCommandList.getNext( stCmdCurrTraceInfo.astTable );
		/* set confluence node as the current node */
		stCmdCurrTraceInfo.astTable = astLeft;
		stCmdCurrTraceInfo.astNext = LinkCommandList.getNext( stCmdCurrTraceInfo.astTable );
		stCmdCurrTraceInfo.pathFlag = PATH_TRUE;
		/* the current COMMAND is ASM_CMD_CONFLUX,
		 * so stTrPathInfo.astCurrBeginNode will be set in tr_PathMakeConflux */
	}
	return rc;
}
static S4 tr_PathMakeFromCmdList( VOID ){
	U4 kind = stCmdListAccess.opKind.get( stCmdCurrTraceInfo.astTable );
	TRY;
	Tr_PrintfCmdList( stCmdCurrTraceInfo.astTable );
	switch(kind){
	case ASM_CMD_RETURN  :
		return  tr_PathMakeReturn();
	case ASM_CMD_CONFLUX  :
	case ASM_CMD_CHOOSEEND  :
		return  tr_PathMakeConflux();
	case ASM_CMD_JUMP  :
		return  tr_PathMakeJump();
	case ASM_CMD_BRANCH  :
	case ASM_CMD_CHOOSE  :
		return  tr_PathMakeBranch();
	case ASM_CMD_FUNCEXIT  :
		return  tr_PathMakeExit();
	}
	/* for other COMMANDs:
	 *  no effect for PATH(control-flow), so just go ahead */
	stCmdCurrTraceInfo.pathFlag = PATH_TRUE;
	stCmdCurrTraceInfo.astTable = stCmdCurrTraceInfo.astNext;
	stCmdCurrTraceInfo.astNext = LinkCommandList.getNext( stCmdCurrTraceInfo.astTable );
	CATCH( TRACEEXIT_FATAL );
	return TRACEEXIT_SUCCESS;
}
/* main loop for making PATH */
static S4  tr_PathMakeLoop( VOID ){
	S4 rc = TRACEEXIT_SUCCESS;

	while( rc == TRACEEXIT_SUCCESS ){
		if(  stCmdCurrTraceInfo.astTable < MIN_ARRAY ){
			/* pop BRANCH from stack */
			rc = Tr_StkCmdProcess( STACK_PULL );
			if( rc != TRACEEXIT_SUCCESS ){
				continue;
			}
		}
		if(  stCmdCurrTraceInfo.astTable < MIN_ARRAY ) {
			continue;
		}
		rc = tr_PathMakeFromCmdList();
		if( rc == TRACEEXIT_FATAL ){
			continue;
		}
	}
	if( rc == TRACEEXIT_END )
	{
		rc = TRACEEXIT_SUCCESS;
	}
	return ( rc );
}
/* return true if there are multi-IN-PATHs */
static BOOL tr_PathComIsMultiInput( AST astPathInfo ){
	astPathInfo = stCmdPathInfoAccess.pathIn.get( astPathInfo );
	if( stCmdPathInfoAccess.pathIn_next.get( astPathInfo ) ){
		return TRUE;
	}
	return FALSE;
}
/* return true if there are multi-OUT-PATHs */
static BOOL tr_PathComIsMultiOutput( AST astPathInfo ){
	astPathInfo = stCmdPathInfoAccess.pathOut.get( astPathInfo );
	if( stCmdPathInfoAccess.pathOut_next.get( astPathInfo ) ){
		return TRUE;
	}
	return FALSE;
}
/***********************************************
 * FUNCTIONS for MAKING LOOPs
 ***********************************************/
/* return true if "astPathInfo" had been traced. it's the begin PATH of a loop */
static BOOL tr_PathLoopIsTracedPath( AST astPathInfo ){
	AST astPathChain = stCmdCurrTraceInfo.astPathParam;
	AST astTredPathInfo;
	/* stCmdRecordingAccess: restore the chain of PATHs that were traced */
	while( astPathChain > 0 ){
		astTredPathInfo = stCmdRecordingAccess.parameter.get( astPathChain );
		if( astTredPathInfo == astPathInfo ){
			return TRUE;
		}
		astPathChain = stCmdRecordingAccess.before.get( astPathChain );
	}
	return FALSE;
}
/* For a PATH who has multi-IN-PATHs,
 *   return TRUE if all IN-PATHs were traced */
static BOOL tr_PathLoopIsAllInputTraced( AST astPath ){
	AST astInPath = stCmdPathInfoAccess.pathIn.get( astPath );
	BOOL flag = TRUE;

	while( astInPath ){
		/* if traced, the property "times" will be not zero */
		if( stCmdPathInfoAccess.times.get( astInPath ) == 0 ){
			flag = FALSE;
			break;
		}
		astInPath = stCmdPathInfoAccess.pathIn_next.get( astInPath );
	}
	return flag;
}
/* For a PATH who has multi-OUT-PATHs,
 *   return TRUE if all OUT-PATHs were traced */
static BOOL tr_PathLoopIsAllOutputTraced( AST astPath ){
	AST astOutPath = stCmdPathInfoAccess.pathOut.get( astPath );
	BOOL flag = TRUE;

	while( astOutPath ){
		/* if traced, the property "times" will be not zero */
		if( stCmdPathInfoAccess.times.get( astOutPath ) == 0 ){
			flag = FALSE;
			break;
		}
		astOutPath = stCmdPathInfoAccess.pathOut_next.get( astOutPath );
	}
	return flag;
}
/* Restore the information to PATH stack */
static VOID tr_PathLoopRecordInfo( AST astStack ){
	stTrPathStkAccess.currPathInfo.set( astStack, stCmdCurrTraceInfo.astPath );
	stTrPathStkAccess.nextPathInfo.set( astStack, stCmdCurrTraceInfo.astPathNext );
	/* for making LOOP,
	 * the last one of stCmdRecordingAccess chain is
	 * restored to stCmdCurrTraceInfo.astPathParam. */
	stTrPathStkAccess.pathParam.set( astStack, stCmdCurrTraceInfo.astPathParam );
}
/* If there were some BRANCH commands in the current stCmdRecordingAccess chain,
 *  get the BRANCH that is not traced yet */
static AST tr_PathLoopPopBranch( VOID ){
	AST astRecord = stCmdCurrTraceInfo.astPathParam;
	AST astPathInfo;
	AST astBranch=0;

	trace_path_log("\ttry to pop %ld ", stCmdRecordingAccess.parameter.get( astRecord ) );
	while( astRecord > 0 ){
		/* loop back. search from the end to begin */
		astPathInfo = stCmdRecordingAccess.parameter.get( astRecord );
		if( tr_PathComIsMultiOutput( astPathInfo )){
			/* multi OUT-PATHs */
			if( !tr_PathLoopIsAllOutputTraced( astPathInfo )){
				/* there is a branch that is not traced yet */
				astBranch = stCmdPathInfoAccess.pathOut.get( astPathInfo );
				while( astBranch ){
					if( stCmdPathInfoAccess.times.get( astBranch ) == 0 ){
						break;
					}
					astBranch = stCmdPathInfoAccess.pathOut_next.get( astBranch );
				}
				/* update the stCmdRecordingAccess chain */
				stCmdCurrTraceInfo.astPathParam = astRecord;
				break;
			}
		}
		astRecord = stCmdRecordingAccess.before.get( astRecord );
	}
	/* the branch that is not traced yet */
	return astBranch;
}
/* For the latest PATH that has multi-IN-PATHs.
 * go to NEXT if all IN-PATHS are traced.  */
static VOID tr_PathLoopPopTracedAllInput( VOID ){
	AST astBrStk;
	AST astTrPathInfo = 0;
	astBrStk = stTrPathStkAccess.getMax();
	if( astBrStk > 0 ){
		astTrPathInfo = stTrPathStkAccess.nextPathInfo.get( astBrStk );
		/* the latest PATH == the top of stack */
		if( tr_PathLoopIsAllInputTraced( astTrPathInfo )){
			stCmdCurrTraceInfo.astPath = astTrPathInfo;
			stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( astTrPathInfo );
			/* update the stCmdRecordingAccess chain from the stack */
			stCmdCurrTraceInfo.astPathParam = stTrPathStkAccess.pathParam.get( astBrStk );
			stTrPathStkAccess.alloc(-1);
		}
	}
}
/* For the latest PATH that has multi-IN-PATHs in stack  */
static VOID tr_PathLoopPopStack( VOID ){
	AST astBrStk;
	astBrStk = stTrPathStkAccess.getMax();
	if( astBrStk > 0 ){
		stCmdCurrTraceInfo.astPath = stTrPathStkAccess.nextPathInfo.get( astBrStk );
		stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
		/* update the stCmdRecordingAccess chain from the stack */
		stCmdCurrTraceInfo.astPathParam = stTrPathStkAccess.pathParam.get( astBrStk );
		stTrPathStkAccess.alloc(-1);
	}
}

/* Is the confluence node in the stack.
 * return index when the confluence node is in the stack.
 * return 0 when the confluece node is not in the stack. */
static AST tr_PathLoopCheckStack( AST astPathConflux ){
	AST astBrStk;
	AST astPathRecord;

	astBrStk = stTrPathStkAccess.getMax();
	while( astBrStk > 0 ){
		astPathRecord = stTrPathStkAccess.nextPathInfo.get( astBrStk );
		if( astPathRecord == astPathConflux ){
			break;
		}
		astBrStk--;
	}
	return astBrStk;
}
/* push PATH that has multi-IN-PATHS */
/* NOTICE: Only a PATH that has multi-IN-PATHS will be pushed */
static VOID tr_PathLoopStackPush( VOID ){
	AST astPathConflux = stCmdCurrTraceInfo.astPathNext;
	AST astBrStk = tr_PathLoopCheckStack(astPathConflux);
	if( astBrStk == 0 ){
		/* the confluece node is not in the stack. push it */
		stTrPathStkAccess.alloc(1);
		astBrStk = stTrPathStkAccess.getMax();
		tr_PathLoopRecordInfo( astBrStk );
	}else{
		/* the confluece node is in the stack. do nothing */
	}
}
/* Set the LOOP to every COMMAND which belongs to the LOOP by PATH */
static VOID tr_PathLoopSetToNode( AST astLoopInfo, AST astPath ){
	/* astLoopInfo : new LOOP */
	/* astPath: a PATH in the new LOOP(astLoopInfo) */
	AST astCmdList;
	AST astCmdEnd;
	AST astOldLoop;

	astCmdList = stCmdPathInfoAccess.beginNode.get( astPath );
	astCmdEnd = stCmdPathInfoAccess.endNode.get( astPath );
	while( astCmdList ){
		astOldLoop = stCmdListMetaAccess.loopInfo.get( astCmdList );
		if( astOldLoop == 0 ){
			trace_path_log("SET LOOP->NODE:%ld %ld \n", astLoopInfo, astCmdList );
			stCmdListMetaAccess.loopInfo.set( astCmdList, astLoopInfo );
		}
		if( astCmdList == astCmdEnd ){
			break;
		}
		/* get NEXT COMMAND in "astPath" */
		astCmdList = TraceCmdGetNextByPath( astCmdList, astPath );
	}
}
/* For searching all PATHs in the new LOOP.
 *  Check whether astLastestPath is in current stCmdRecordingAccess chain.
 *  THE  stCmdRecordingAccess chain:
 *    if bForwad is true: astPathChain is the begin of stCmdRecordingAccess chain.
 *       search forward until astPathEnd.
 *    if bForwad is false: astPathChain is the end of stCmdRecordingAccess chain.
 *       search backward until astPathEnd. */
static BOOL tr_PathLoopIsInPathChain( AST astPathChain, AST astPathEnd, AST astLastestPath, BOOL bForwad ){
	AST astTredPathInfo;
	while( astPathChain > 0 ){
		astTredPathInfo = stCmdRecordingAccess.parameter.get( astPathChain );
		if( astTredPathInfo == astLastestPath ){
			return TRUE;
		}
		if( astTredPathInfo == astPathEnd ){
			break;
		}
		if( bForwad ){
			astPathChain = stCmdRecordingAccess.next.get( astPathChain );
		}else{
			astPathChain = stCmdRecordingAccess.before.get( astPathChain );
		}
	}
	return FALSE;
}
/* For searching all PATHs in the new LOOP.
 *  Check whether astLastestPath is in current LOOP.
 *  When there are some if-statements in the loop,
 *   only the FALSE-PATHs of if-statements are in the stCmdRecordingAccess chain.
 *  Then, it must be checked whether the TRUE-PATHs of if-statements are in current LOOP */

static BOOL tr_PathLoopIsInLoop( AST astPathChain, AST astPathEnd, AST astLastestPath ){
	/* The PATH is in the LOOP */
	if( tr_PathLoopIsInPathChain( astPathChain, astPathEnd, astLastestPath, FALSE )){
		return TRUE;
	}
	astLastestPath = stCmdPathInfoAccess.pathIn.get( astLastestPath );
	if( astLastestPath == 0 ){
		return FALSE;
	}
	/* The PATH is in the LOOP when its IN-PATH and OUT-PATH are both in the LOOP */
	while( astLastestPath ){
		if( tr_PathLoopIsInLoop( astPathChain, astPathEnd, astLastestPath ) ){
			return TRUE;
		}
		astLastestPath = stCmdPathInfoAccess.pathIn_next.get( astLastestPath );
	}
	return FALSE;
}
/* Set the new LOOP to the PATH that belongs to the LOOP */
static VOID tr_PathLoopSetToPath( AST astLoopInfo, AST astPathChain, AST astPath ){
	/* astLoopInfo: the new LOOP */
	/* astPathChain: last node of stCmdRecordingAccess chain */
	/* astPath: the PATH */
	AST astOldLoop;
	AST astOldLoopParent=0;
	AST astFirstPath=0;
	trace_path_log("SET LOOP->PATH:%ld %ld ", astLoopInfo, astPath );
	astOldLoop = stCmdPathInfoAccess.loopInfo.get( astPath );
	while( astOldLoop > 0 ){
		if( astOldLoop == astLoopInfo ){
			/* already be set */
			trace_path_log("added\n");
			return;
		}
		astOldLoopParent = astOldLoop;
		astOldLoop = stCmdLoopInfoAccess.parent.get( astOldLoopParent );
	}
	astFirstPath = stCmdLoopInfoAccess.begin.get( astLoopInfo );
	if( tr_PathLoopIsInLoop( astPathChain, astFirstPath, astPath ) ){
		/* If the PATH is in the new LOOP */
		if( astOldLoopParent == 0 ){
			/* there is not child LOOP */
			trace_path_log("add to node\n");
			stCmdPathInfoAccess.loopInfo.set( astPath, astLoopInfo );
			tr_PathLoopSetToNode( astLoopInfo, astPath );
		}else{
			/* there is some child LOOPs */
			/* the new LOOP is added as the parent-LOOP of child LOOP,
			 * so it does not need to set the LOOP to COMMANDs and PATH */
			trace_path_log("add as father\n");
			stCmdLoopInfoAccess.parent.set( astOldLoopParent, astLoopInfo );
		}

		if( stCmdLoopInfoAccess.begin.get( astLoopInfo ) == astPath ){
			/* Finished until the begin PATH of the LOOP */
			return;
		}

		astPath = stCmdPathInfoAccess.pathIn.get( astPath );
		while( astPath ){
			/* Set the LOOP to PATHs recursively */
			tr_PathLoopSetToPath( astLoopInfo, astPathChain, astPath );
			astPath = stCmdPathInfoAccess.pathIn_next.get( astPath );
		}
	}
	/* else: do nothing if the PATH is not in the new LOOP */
}
/* Fould a loop, and make a new LOOP */
/*
 *     /------\                one loop
 *     \---/--/-----\
 *         \--------/
 *
 *
 *     /-----------\
 *    /  /-------\  \        two loops (nesting)
 *    \  \-------/  /
 *     \-----------/
 */
static VOID tr_PathLoopNew( AST astFirstPath, AST astLastestPath ){
	AST astLoopInfo;
	AST astPathChain = stCmdCurrTraceInfo.astPathParam;
	AST astOldLoop;
	AST astPathInChain;

	astOldLoop = stCmdPathInfoAccess.loopInfo.get( astFirstPath );
	if( astOldLoop > 0 ){
		/* For the entry PATH of a loop:
		 *  If there was a LOOP already, the paths belong to the same loop,
		 *  so do not make a new one.
		 */
		astLoopInfo = astOldLoop;
	}else{
		/* For the entry PATH of a loop:
		 *  add a new LOOP.
		 */
		stCmdLoopInfoAccess.alloc(1);
		astLoopInfo = stCmdLoopInfoAccess.getMax();
		stCmdLoopInfoAccess.begin.set( astLoopInfo, astFirstPath );
	}
	trace_path_log("LOOP:%ld %ld %ld >>>>>>>>>>>>>>>>\n", astLoopInfo, astFirstPath, astLastestPath );
	while( astPathChain > 0 ){
		/* For every PATH in stCmdRecordingAccess chain */
		/* Set the LOOP to every PATH that belongs to it */
		/* back trace */
		astPathInChain = stCmdRecordingAccess.parameter.get( astPathChain );
		astLastestPath = astPathInChain;
		/* For all IN-PATHs */
		while( astLastestPath ){
			tr_PathLoopSetToPath(astLoopInfo, astPathChain, astLastestPath);
			astLastestPath = stCmdPathInfoAccess.pathIn_next.get( astLastestPath );
			trace_path_log("---------------\n");
		}
		if( astPathInChain == astFirstPath ){
			break;
		}
		astPathChain = stCmdRecordingAccess.before.get( astPathChain );
	}
}
/* main loop for making LOOP */
static VOID tr_PathLoopCollectInfo( AST astFunction ){
	AST astRecord;

	stCmdStackAccess.clear();
	stTrPathStkAccess.clear();
	stCmdRecordingAccess.clear();
	stCmdCurrTraceInfo.astPath = stTrFunctionAccess.pathInfo.get( astFunction );
	stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
	stCmdCurrTraceInfo.astTable = 0;
	stCmdCurrTraceInfo.astPathParam = 0;
	while( stCmdCurrTraceInfo.astPath ){
		trace_path_log("path:%ld->%ld\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
		if( stCmdPathInfoAccess.times.get(  stCmdCurrTraceInfo.astPath  )){
			trace_path_log("\t traced:%ld->%ld\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
			/* traced, skip */
			stCmdCurrTraceInfo.astPath = 0;
			stCmdCurrTraceInfo.astPathNext = 0;
		}else{
			/* set "traced" */
			stCmdPathInfoAccess.times.set(  stCmdCurrTraceInfo.astPath, 1 );
			/* record the PATH to stCmdRecordingAccess */
			stCmdRecordingAccess.alloc(1);
			astRecord = stCmdRecordingAccess.getMax();
			stCmdRecordingAccess.parameter.set( astRecord, stCmdCurrTraceInfo.astPath );
			stCmdRecordingAccess.before.set( astRecord, stCmdCurrTraceInfo.astPathParam );
			stCmdRecordingAccess.next.set( stCmdCurrTraceInfo.astPathParam, astRecord );
			/* update the last one */
			stCmdCurrTraceInfo.astPathParam = astRecord;
			if( tr_PathLoopIsTracedPath( stCmdCurrTraceInfo.astPathNext ) ){
				/* the path is in the stCmdRecordingAccess chain, so it's a loop */
				/* make a new LOOP, and stop to trace branches or next of loop */
				tr_PathLoopNew( stCmdCurrTraceInfo.astPathNext,
						stCmdCurrTraceInfo.astPath );
				stCmdCurrTraceInfo.astPath = 0;
				stCmdCurrTraceInfo.astPathNext = 0;
			}else{
				if( tr_PathComIsMultiInput (stCmdCurrTraceInfo.astPathNext)
						&& !tr_PathLoopIsAllInputTraced( stCmdCurrTraceInfo.astPathNext )  ){
					/* multi-in-path: confluence path */
					trace_path_log("\t push:%ld->%ld\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
					/* Only push the multi-IN-PATH to stack
					 * For the efficiency of tracing algorithm,
					 *    n*2 but not n^2 */
					tr_PathLoopStackPush( );
					stCmdCurrTraceInfo.astPath = 0;
					stCmdCurrTraceInfo.astPathNext = 0;
				}else{
					/* go ahead */
					stCmdCurrTraceInfo.astPath = stCmdCurrTraceInfo.astPathNext;
					stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
				}
			}
		}
		/* When stCmdCurrTraceInfo.astPath is 0, try get PATH as below */
		if( stCmdCurrTraceInfo.astPath == 0 ){
			trace_path_log("path==0\n" );
			/* 1. try stCmdCurrTraceInfo.astPathNext */
			stCmdCurrTraceInfo.astPath = stCmdCurrTraceInfo.astPathNext;
			stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
		}
		if( stCmdCurrTraceInfo.astPath == 0 ){
			/* 2. try branch PATH in stCmdRecordingAccess chain */
			/* get the branch node that is not traced in current path-chain  */
			stCmdCurrTraceInfo.astPath = tr_PathLoopPopBranch( );
			stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
			trace_path_log("\tpop branch:%ld->%ld\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
		}
		if( stCmdCurrTraceInfo.astPath == 0 ){
			/* 3. try to pop the multi-IN_PATH from the top of stack,
			 * only when all of its IN-PATHs are traced */
			tr_PathLoopPopTracedAllInput( );
			trace_path_log("\tpop traced confluence:%ld->%ld\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
		}
		if( stCmdCurrTraceInfo.astPath == 0 ){
			/* 4. pop the stack */
			/* There is not branch node that is not traced in current stCmdRecordingAccess chain  */
			/* pop the multi-IN_PATH from stack, and go ahead */
			tr_PathLoopPopStack( );
			trace_path_log("\tpop confluence:%ld->%ld\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
		}
	}
	stCmdStackAccess.clear();
	stTrPathStkAccess.clear();
	stCmdRecordingAccess.clear();
}

VOID Tr_PathCollectPathTree( AST astTrFunction ){
//	S4 rc;
	CMDTRACEOPTION temp; /* restore stCmdTraceOption which is set by user */
	AST astFunction = stTrFunctionAccess.function.get( astTrFunction );
	if( !Tr_FuncIsPathCollected(astTrFunction) ){
		 /*  no mark */
		if( LinkFunction.getFunctionEntry( astFunction ) > 0 ){
			stCmdStackAccess.clear();
			temp = stCmdTraceOption;
			stCmdTraceOption.ucLoopOption = 1;
			stCmdTraceOption.ucCallFuncBody = 0;

			stCmdCurrTraceInfo.astTable = LinkFunction.getFunctionEntry( astFunction );
			stCmdCurrTraceInfo.astFunction = astTrFunction;
			stCmdCurrTraceInfo.astNext = LinkCommandList.getNext( stCmdCurrTraceInfo.astTable );
			stCmdCurrTraceInfo.pathFlag = PATH_TRUE;

			stTrPathInfo.astCurrBeginNode = stCmdCurrTraceInfo.astTable;
			stTrPathInfo.condition = PATH_TRUE;/* no controller( no conditions ) */
			stTrPathInfo.astBegin = 0;/* to restore the first PATH */
			 /*  make PATHs */
			/*rc =*/ tr_PathMakeLoop();
			stTrFunctionAccess.pathInfo.set( astTrFunction, stTrPathInfo.astBegin );

			 /*  make LOOPs */
			tr_PathLoopCollectInfo( astTrFunction );
			 /*  mark the function */
			Tr_FuncSetPathCollected(astTrFunction);
			stCmdRecordingAccess.clear();
			stCmdStackAccess.clear();
#ifdef DEBUG
			{
				AST astMin;
				AST astMax;
				astMax=stCmdPathInfoAccess.getMax();
				for( astMin = MIN_ARRAY; astMin <= astMax; astMin++ ){
					Tr_PrintfPathInfo( astMin );
				}
				astMax=stCmdLoopInfoAccess.getMax();
				for( astMin = MIN_ARRAY; astMin <= astMax; astMin++ ){
					Tr_PrintfLoopInfo( astMin );
				}
			}
#endif
	//	#ifdef DEBUG
	//		{
	//			AST astMin;
	//			AST astMax=LinkCommandList.getMax();
	//			for( astMin = MIN_ARRAY; astMin <= astMax; astMin++ ){
	//				Tr_PrintfCmdList( astMin );
	//			}
	//		}
	//	#endif
			stCmdTraceOption = temp;
			stCmdStackAccess.clear();
		}
	}
}
/***********************************************
 * FUNCTIONS for tracing
 ***********************************************/
/* return true if the astPath PATH is in the astLoop LOOP */
static BOOL tr_PathIsInCurrLoop( AST astPath, AST astLoop ){
	BOOL bInLoop = FALSE;
	AST astLoopInfo;
	if( astLoop > 0 ){
		astLoopInfo = stCmdPathInfoAccess.loopInfo.get( astPath );
		while( astLoopInfo ){
			/* Also check the parent LOOPs */
			if( astLoopInfo == astLoop ){
				bInLoop = TRUE;
				break;
			}
			astLoopInfo = stCmdLoopInfoAccess.parent.get( astLoopInfo );
		}
	}
	return bInLoop;
}
/* return true if the astPath PATH is the begin PATH of a LOOP */
static BOOL tr_PathIsLoopBeginNode( AST astPath ){
	BOOL bInLoop = FALSE;
	AST astLoopInfo;
	astLoopInfo = stCmdPathInfoAccess.loopInfo.get( astPath );
	/* It's impossible that astPath is the begin PATH of parent LOOPs.
	 * so do not check parent LOOPs */
	if( astLoopInfo ){
		if( astPath == stCmdLoopInfoAccess.begin.get( astLoopInfo )){
			bInLoop = TRUE;
		}
		astLoopInfo = stCmdLoopInfoAccess.parent.get( astLoopInfo );
	}
	return bInLoop;
}
/* return true if the astPath PATH is the begin PATH of the astLoop LOOP */
static BOOL tr_PathIsBeginNodeOfCurrLoop( AST astPath, AST astLoop ){
	BOOL bInLoop = FALSE;
	if( astLoop > 0 ){
		if( astPath == stCmdLoopInfoAccess.begin.get( astLoop )){
			bInLoop = TRUE;
		}
	}
	return bInLoop;
}
/* return true if the astPathInfo PATH is traced */
static BOOL tr_PathIsTracedPath( AST astPathInfo ){
	AST astLoopInfo = stCmdCurrTraceInfo.astLoop;
	U2  timesPath = stCmdPathInfoAccess.times.get ( astPathInfo );

	if( astLoopInfo == 0 ){
		/* Outside of LOOP */
		if( timesPath > 0 ){
			return TRUE;
		}
	}else{
		/* Inside of LOOP */
		U2  timesLoop = stCmdLoopInfoAccess.times.get ( astLoopInfo );
		if( timesPath == timesLoop ){
			return TRUE;
		}
	}
	return FALSE;
}
/* return true if all IN-PATHs of astPath PATH are traced */
static BOOL tr_PathIsAllInputTraced( AST astPath ){
	AST astInPath = stCmdPathInfoAccess.pathIn.get( astPath );
	BOOL flag = TRUE;

	while( astInPath ){
		if( !tr_PathIsTracedPath( astInPath ) ){
			flag = FALSE;
			break;
		}
		astInPath = stCmdPathInfoAccess.pathIn_next.get( astInPath );
	}
	return flag;
}
//static BOOL tr_PathIsAllOutputTraced( AST astPath ){
//	AST astOutPath = stCmdPathInfoAccess.pathOut.get( astPath );
//	BOOL flag = TRUE;
//
//	while( astOutPath ){
//		if( !tr_PathIsTracedPath( astOutPath ) == 0 ){
//			flag = FALSE;
//			break;
//		}
//		astOutPath = stCmdPathInfoAccess.pathOut_next.get( astOutPath );
//	}
//	return flag;
//}

//static AST tr_PathPopBranch( VOID ){
//	AST astRecord = stCmdCurrTraceInfo.astPathParam;
//	AST astPathInfo;
//	AST astBranch=0;
//	if( stCmdCurrTraceInfo.loopFlg != LOOP_FLG_IN ){
//		while( astRecord > 0 ){
//			astPathInfo = stCmdRecordingAccess.parameter.get( astRecord );
//			if( tr_PathComIsMultiOutput( astPathInfo )){
//				trace_path_log2("\ttry to pop %ld ", astPathInfo );
//				astBranch = stCmdPathInfoAccess.pathOut.get( astPathInfo );
//				while( astBranch ){
//					if( !tr_PathIsInCurrLoop( astPathInfo, stCmdCurrTraceInfo.astLoop )
//						&& !tr_PathIsTracedPath( astBranch )){
//						break;
//					}
//					astBranch = stCmdPathInfoAccess.pathOut_next.get( astBranch );
//				}
//				trace_path_log2("\n" );
//				if( astBranch != 0 ){
//					stCmdCurrTraceInfo.astPathParam = astRecord;
//				}
//			}
//
//			astRecord = stCmdRecordingAccess.before.get( astRecord );
//		}
//	}
//	return astBranch;
//}
//static VOID tr_PathPopTracedAllInput( VOID ){
//	AST astBrStk;
//	AST astTrPathInfo = 0;
//	if( stCmdCurrTraceInfo.loopFlg != LOOP_FLG_IN ){
//	astBrStk = stTrPathStkAccess.getMax();
//	if( astBrStk > 0 ){
//		astTrPathInfo = stTrPathStkAccess.nextPathInfo.get( astBrStk );
//		if( tr_PathLoopIsAllInputTraced( astTrPathInfo )){
//			stCmdCurrTraceInfo.astPath = astTrPathInfo;
//			stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( astTrPathInfo );
//			stCmdCurrTraceInfo.astPathParam = stTrPathStkAccess.pathParam.get( astBrStk );
//			stTrPathStkAccess.alloc(-1);
//		}
//	}
//	}
//}
/* When in a LOOP,
 * return true if PATH stack of current LOOP is empty
 * When out of a LOOP,
 * return true if PATH stack of current FUNCTION is empty */
static BOOL tr_PathIsEmptyStack( VOID){
	AST astBrStk;
	astBrStk = stTrPathStkAccess.getMax();
	if( astBrStk > stCmdCurrTraceInfo.astPathStkBottom ){
		return FALSE;
	}
	return TRUE;
}
//static VOID tr_PathPopStack( VOID ){
//	AST astBrStk;
//	if( stCmdCurrTraceInfo.loopFlg != LOOP_FLG_IN ){
//	astBrStk = stTrPathStkAccess.getMax();
//	if( astBrStk > 0 ){
//		Tr_StkPathProcess( STACK_PULL );
//	}
//	}
//}
//static VOID tr_PathPopTracedAllInputInLoop( VOID ){
//	AST astBrStk;
//	AST astTrPathInfo = 0;
//
//	astBrStk = stTrPathStkAccess.getMax();
//	if( astBrStk > 0 ){
//		astTrPathInfo = stTrPathStkAccess.nextPathInfo.get( astBrStk );
//		if( tr_PathIsAllInputTraced( astTrPathInfo )){
//			if( stCmdCurrTraceInfo.astLoop == 0 || tr_PathIsInCurrLoop( astTrPathInfo, stCmdCurrTraceInfo.astLoop )){
//				stCmdCurrTraceInfo.astPath = astTrPathInfo;
//				stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( astTrPathInfo );
//				stCmdCurrTraceInfo.astPathParam = stTrPathStkAccess.pathParam.get( astBrStk );
//				stTrPathStkAccess.alloc(-1);
//			}
//		}
//	}
//}
//static AST tr_PathPopBranchInLoop( VOID ){
//	AST astRecord = stCmdCurrTraceInfo.astPathParam;
//	AST astPathInfo;
//	AST astBranch=0;
//	if(  stCmdCurrTraceInfo.astLoop == 0 ){
//		return tr_PathPopBranch();
//	}
//	while( astRecord > 0 ){
//		astPathInfo = stCmdRecordingAccess.parameter.get( astRecord );
//		if( tr_PathComIsMultiOutput( astPathInfo )){
//			if( !tr_PathIsAllOutputTraced( astPathInfo )){
//				astBranch = stCmdPathInfoAccess.pathOut.get( astPathInfo );
//				while( astBranch ){
//					if( tr_PathIsInCurrLoop( astBranch, stCmdCurrTraceInfo.astLoop )){
//						if( stCmdCurrTraceInfo.loopFlg == LOOP_FLG_IN ){
//							if( stCmdPathInfoAccess.times.get( astBranch ) != stCmdLoopInfoAccess.times.get( stCmdCurrTraceInfo.astLoop ) ){
//								stCmdPathInfoAccess.times.set( astBranch,  stCmdLoopInfoAccess.times.get( stCmdCurrTraceInfo.astLoop ) );
//								stCmdCurrTraceInfo.astPathParam = astRecord;
//								break;
//							}
//						}
//					}
//					astBranch = stCmdPathInfoAccess.pathOut_next.get( astBranch );
//				}
//			}
//		}
//		astRecord = stCmdRecordingAccess.before.get( astRecord );
//	}
//	return astBranch;
//}
//static VOID tr_PathPopStackInLoop( VOID ){
//	AST astBrStk;
//	AST astPathInfo;
//
//	if( stCmdCurrTraceInfo.astLoop == 0 ){
//		tr_PathPopStack();
//		return;
//	}
//	astBrStk = stTrPathStkAccess.getMax();
//	if( astBrStk > 0 ){
//		astPathInfo = stTrPathStkAccess.nextPathInfo.get( astBrStk );
//		if( tr_PathIsInCurrLoop( astPathInfo, stCmdCurrTraceInfo.astLoop )){
//			if( !tr_PathIsCurrLoopBeginNode( astPathInfo, stCmdCurrTraceInfo.astLoop )){
//				stCmdCurrTraceInfo.astPath = astPathInfo;
//				stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
//				stCmdCurrTraceInfo.astPathParam = stTrPathStkAccess.pathParam.get( astBrStk );
//				stTrPathStkAccess.alloc(-1);
//			}
//		}
//	}
//}
/* Check whether the LOOP should be over,
 * and reset the  stCmdCurrTraceInfo.astPath */
static S4 tr_PathTrytoLeaveCurrLoop( VOID ){
	S4 rc = TRACEEXIT_SUCCESS;
	U2 times;
//	AST astBrStk;
	if( stCmdCurrTraceInfo.loopFlg == LOOP_FLG_IN
		&& stCmdCurrTraceInfo.astLoop > 0 ){
		/* in a LOOP */
//		astBrStk = stTrPathStkAccess.getMax();
		times = stCmdLoopInfoAccess.times.get( stCmdCurrTraceInfo.astLoop );
		if( times >= stCmdTraceOption.ucLoopOption ){
			/* The traced times of current LOOP reaches to the setting times */
			/* Stop */
			stCmdCurrTraceInfo.astPath = 0;
			stCmdCurrTraceInfo.astPathNext = 0;
			stCmdCurrTraceInfo.astPathParam = 0;
		}else{
			/* The traced times of current LOOP doesn't reach to the setting times */
			/* increase the times, and trace from the begin PATH of the LOOP */
			stCmdLoopInfoAccess.times.set( stCmdCurrTraceInfo.astLoop, times+1 );
			stCmdCurrTraceInfo.astPath = stCmdLoopInfoAccess.begin.get( stCmdCurrTraceInfo.astLoop );
			stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
		}
	}
	return rc;
}
/* Add EXIT-PATH ( the branches that do not belong to current LOOP ) of current LOOP */
static VOID tr_PathAddLoopExit( VOID ){
	AST astLoopExit;
	AST astCnt = stCmdCurrTraceInfo.astLoopExitBottom + 1;
	AST astMax = stCmdLoopExitAccess.getMax();
	AST astPath;
	AST astPathNext;
	AST astParam;
	for( ; astCnt <= astMax; astCnt++ ){
		if( stCmdCurrTraceInfo.astLoop == stCmdLoopExitAccess.loop.get( astCnt ) ){
			astPath = stCmdLoopExitAccess.path.get( astCnt );
			astPathNext = stCmdLoopExitAccess.next.get( astCnt );
			if( stCmdCurrTraceInfo.astPath == astPath
				&& stCmdCurrTraceInfo.astPathNext == astPathNext ){
				/* added, do not add it for twice */
				astParam = stCmdLoopExitAccess.pathParam.get( astCnt );
				if( astParam != 0 ){
					Tr_PathParamOrMergeTo( stCmdCurrTraceInfo.astPathParam, astParam );
				}else{
					astParam = Tr_PathParamCopyNew( stCmdCurrTraceInfo.astPathParam );
				}
				stCmdLoopExitAccess.pathParam.set( astCnt, astParam );
				return;
			}
		}
	}
	/* add loop exit */
	stCmdLoopExitAccess.alloc(1);
	astLoopExit = stCmdLoopExitAccess.getMax();
	stCmdLoopExitAccess.loop.set( astLoopExit,  stCmdCurrTraceInfo.astLoop  );
	stCmdLoopExitAccess.path.set( astLoopExit, stCmdCurrTraceInfo.astPath);
	stCmdLoopExitAccess.next.set( astLoopExit, stCmdCurrTraceInfo.astPathNext );
	stCmdLoopExitAccess.pathParam.set( astLoopExit, stCmdCurrTraceInfo.astPathParam );
	astParam = Tr_PathParamCopyNew( stCmdCurrTraceInfo.astPathParam );
	stCmdLoopExitAccess.pathParam.set( astCnt, astParam );
}
/* Process of the PATH which has multi-OUT-PATHs */
static S4 tr_PathProcessBranch( VOID ){
	AST astNextPath;
	AST astBrother;
	S4 rc = TRACEEXIT_SUCCESS;
	AST astParam;

	/* branch */
	astNextPath = 0;
	astBrother = stCmdCurrTraceInfo.astPathNext;
	while( astBrother ){
		/* for OUT-PATH that is not traced */
		if( stCmdCurrTraceInfo.astLoop > 0 ){
			/* In a LOOP */
			if( tr_PathIsInCurrLoop( astBrother, stCmdCurrTraceInfo.astLoop ) ){
				/* branch in LOOP  */
				if( astNextPath == 0 ){
					/* record the first branch PATH,
					 * it will be next PATH (stCmdCurrTraceInfo.astPathNext) */
					astNextPath = astBrother;
				}else{
					/* push other branch PATHs into stack  */
					stCmdCurrTraceInfo.astPath = astBrother; /* OUT-PATH */
					stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( astBrother );
					trace_path_log2("\tPUSH STACK from %ld\n", stCmdCurrTraceInfo.astPath  );

					astParam = stCmdCurrTraceInfo.astPathParam;
					stCmdCurrTraceInfo.astPathParam = Tr_PathParamCopyNew( astParam );
					Tr_VarBlkReverse( Tr_PathParamGetCurrVariBlock() );
					Tr_StkPathProcess( STACK_PUSH );
					stCmdCurrTraceInfo.astPathParam = astParam;
				}
			}else{
				/* The branch PATH which does not belong to current LOOP.
				 *  For example: break PATH
				 */

				stCmdCurrTraceInfo.astPath = astBrother;
				stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( astBrother );
				trace_path_log2("\tPUSH LOOPEXT:(%ld->%ld)\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
				/* add as loop exit */
				astParam = stCmdCurrTraceInfo.astPathParam;
				stCmdCurrTraceInfo.astPathParam = Tr_PathParamCopyNew( astParam );
				Tr_VarBlkReverse( Tr_PathParamGetCurrVariBlock() );
				tr_PathAddLoopExit();
				stCmdCurrTraceInfo.astPathParam = astParam;
			}
		}else{
			/* outside of loop  */
			if( astNextPath == 0 ){
				/* record the first branch PATH,
				 * it will be next PATH (stCmdCurrTraceInfo.astPathNext) */
				astNextPath = astBrother;
			}else{
				/* push other branch PATHs into stack  */
				stCmdCurrTraceInfo.astPath = astBrother;
				stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( astBrother );
				trace_path_log2("\tPUSH STACK from %ld\n", stCmdCurrTraceInfo.astPathParam  );
				astParam = stCmdCurrTraceInfo.astPathParam;
				stCmdCurrTraceInfo.astPathParam = Tr_PathParamCopyNew( astParam );
				Tr_VarBlkReverse( Tr_PathParamGetCurrVariBlock() );
				Tr_StkPathProcess( STACK_PUSH );
				stCmdCurrTraceInfo.astPathParam = astParam;
			}
		}
		astBrother = stCmdPathInfoAccess.pathOut_next.get( astBrother );
	}
	/* go ahead, the first branch PATH */
	stCmdCurrTraceInfo.astPath = astNextPath;
	stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( astNextPath );
	return rc;
}
/* When a LOOP is finished,
 *  get the branch PATHs in its LOOP-EXIT-stack,
 *  and push them into PATH-stack of parent LOOP/FUNCTION.
 *  and clear the finished LOOP's LOOP-EXIT-stack   */
static VOID tr_PathPushLoopExit2Stack( VOID ){
	AST astCnt, astMax;
	astCnt = stCmdCurrTraceInfo.astLoopExitBottom + 1;
	astMax = stCmdLoopExitAccess.getMax();
	for( ; astCnt <= astMax; astCnt++ ){
		stCmdCurrTraceInfo.astPath = stCmdLoopExitAccess.path.get( astCnt );
		stCmdCurrTraceInfo.astPathNext = stCmdLoopExitAccess.next.get( astCnt );
		stCmdCurrTraceInfo.astPathParam = stCmdLoopExitAccess.pathParam.get( astCnt );
		Tr_StkPathProcess( STACK_PUSH );
	}
	stCmdCurrTraceInfo.astPath = 0;
	stCmdCurrTraceInfo.astPathNext = 0;
	stCmdCurrTraceInfo.astPathParam = 0;
	stCmdLoopExitAccess.alloc( stCmdCurrTraceInfo.astLoopExitBottom - astMax );
}
static BOOL tr_PathIsAllInputNoTrace( AST astPath ){
	astPath = stCmdPathInfoAccess.pathIn.get( astPath );
	while( astPath ){
		if ( stCmdPathInfoAccess.whenBroken.get( astPath ) == 0 ){
			return FALSE;
		}
		astPath = stCmdPathInfoAccess.pathIn_next.get( astPath );
	}
	return TRUE;
}
static VOID tr_PathSetNoTraceFlg( AST astPath ){
	U2 times;
	times = stCmdPathInfoAccess.totalTimes.get( astPath );
	stCmdPathInfoAccess.totalTimes.set( astPath, times+1 );
	if( stCmdCurrTraceInfo.astLoop > 0 ){
		/* same with the LOOP's times if in a LOOP */
		stCmdPathInfoAccess.times.set( astPath,
			stCmdLoopInfoAccess.times.get( stCmdCurrTraceInfo.astLoop ) );
	}else{
		/* set 1 if outside of LOOP */
		stCmdPathInfoAccess.times.set( astPath, 1 );
	}
	stCmdPathInfoAccess.whenBroken.set( astPath,
			stCmdPathInfoAccess.totalTimes.get( astPath ));
	astPath = stCmdPathInfoAccess.pathOut.get( astPath );
	while( astPath ){
		if ( tr_PathIsAllInputNoTrace( astPath )){
			tr_PathSetNoTraceFlg( astPath );
		}
		astPath = stCmdPathInfoAccess.pathOut_next.get( astPath );
	}
}
/* Whether the current PATH is executable   */
static BOOL tr_PathShouldTrace( VOID ){
	/* check the value scope of temporary variables */
	if( Tr_VarBlkHasNoValueVariable( Tr_PathParamGetCurrVariBlock() ) ){
		tr_PathSetNoTraceFlg(stCmdCurrTraceInfo.astPath);
		return FALSE;
	}
	stCmdPathInfoAccess.whenBroken.set( stCmdCurrTraceInfo.astPath, 0 );
	return TRUE;
}
/*  multi-input: more than two. ex. goto & label */
/*  multi-output: two */
/* main loop for tracing PATHs */
S4 Tr_PathLoop( VOID ){
	S4 rc = TRACEEXIT_SUCCESS;
	AST astPathParam=0;
	U2 times = 0;
	/* main loop of trace */
	/* the unit is a PATH in this main loop */
	/* the commands in the same PATH will be traced in Tr_CmdAtOnePath */
	while( rc == TRACEEXIT_SUCCESS ){
		TRY;
		if( stCmdCurrTraceInfo.astPath == 0 ){
			/* stopped somewhere */
			if( stCmdCurrTraceInfo.astLoop > 0 ){
				/* case 1: in LOOP */
				if( tr_PathIsEmptyStack( )){
					trace_path_log2("\tcheck loop:%ld ",stCmdCurrTraceInfo.astLoop  );
					/* case 1-1:the stack is empty, to check loop times.
					 * continue from the start path of loop,(stCmdCurrTraceInfo.astPath>0)
					 * or leaving current loop.(stCmdCurrTraceInfo.astPath==0) */
					tr_PathTrytoLeaveCurrLoop();
				}else{
					trace_path_log2("\tpop stack(loop) from %ld: ", stTrPathStkAccess.getMax() );
					/* case 1-2:the stack is not empty,  pop stack */
					Tr_StkPathProcess( STACK_PULL );
					if( stCmdCurrTraceInfo.astPath > 0 ){
						/* the path may be return or goto, and break multi-loops,
						 * so check it! */
						if( !tr_PathIsInCurrLoop( stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astLoop ) ){
							/* the path does not belongs to current loop.
							 *  break multi-loops, push it as a loop-exit */
							trace_path_log2(" add to loop-exit:(%ld->%ld)\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
							tr_PathAddLoopExit();
							stCmdCurrTraceInfo.astPath = 0;
							continue;
						}else{
							/* go ahead the PATH popped */
							trace_path_log2(" branch in loop(%ld->%ld)\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
						}
					}
				}
				if( stCmdCurrTraceInfo.astPath  ==  0 ){
					/* case 1-1-1: LOOP is finished
					 * leaving a LOOP, push its LOOP-EXIT-PATHs
					 *  into PATH-stack of parent LOOP/FUNCTION.  */
					trace_path_log2(" none, pop loop from %ld\n", stTrLoopStkAccess.getMax() );
					tr_PathPushLoopExit2Stack();
					/* Pop LOOP */
					Tr_StkLoopProcess( STACK_PULL );
					continue;
				}
				/* else: case 1-1-2: continue current LOOP */
			}else{
				/* case 2: out of LOOP */
				if( tr_PathIsEmptyStack( )){
					/* case 2-1: empty stack, stop function */
					trace_path_log2("\tstop function " );
					/* no loop, no branch, function is finished */
					Tr_FunctionExit( stCmdCurrTraceInfo.astFunction );
				}else{
					/* case 2-2: pop stack */
					/* the stack is not empty,  pop stack */
					trace_path_log2("\tpop stack from %ld ", stTrPathStkAccess.getMax() );
					Tr_StkPathProcess( STACK_PULL );
				}
			}
		}
		if( stCmdCurrTraceInfo.astPath == 0 ){
			/* the trace is finished */
			break;
		}
		if( !tr_PathShouldTrace( )){
			/* the current PATH is impossible, so stop */
			stCmdCurrTraceInfo.astPath = 0;
			stCmdCurrTraceInfo.astPathNext = 0;
			continue;
		}
		trace_path_log2("\tprocess:(%ld->%ld)\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
		/* trace commands that are in same path */
		Tr_PrintfBlk( Tr_PathParamGetVariBlock(stCmdCurrTraceInfo.astPathParam));
		rc = Tr_CmdAtOnePath( );
		if( rc != TRACEEXIT_SUCCESS ){
			if( rc == TRACEEXIT_END ){
				/* entered into the callee */
				rc = TRACEEXIT_SUCCESS;
			}
			continue;
		}
		/* reset trace times of current PATH */
		times = stCmdPathInfoAccess.totalTimes.get( stCmdCurrTraceInfo.astPath );
		stCmdPathInfoAccess.totalTimes.set( stCmdCurrTraceInfo.astPath, times+1 );
		if( stCmdCurrTraceInfo.astLoop > 0 ){
			/* same with the LOOP's times if in a LOOP */
			stCmdPathInfoAccess.times.set( stCmdCurrTraceInfo.astPath,
				stCmdLoopInfoAccess.times.get( stCmdCurrTraceInfo.astLoop ) );
		}else{
			/* set 1 if outside of LOOP */
			stCmdPathInfoAccess.times.set( stCmdCurrTraceInfo.astPath, 1 );
		}
		/* Process PATH that has multi-in or multi-out. */
		if( tr_PathIsBeginNodeOfCurrLoop( stCmdCurrTraceInfo.astPathNext, stCmdCurrTraceInfo.astLoop ) ){
			/* the next path is the begin PATH of current LOOP */
			/* stop to pop path stack(pop branch in current loop )(go case 1 ) */
			stCmdCurrTraceInfo.astPath = 0;
			stCmdCurrTraceInfo.astPathNext = 0;
		}else{
			/* the next path is NOT the begin path of current loop */
			if( tr_PathComIsMultiOutput(stCmdCurrTraceInfo.astPath) ){
				/* branch path: current path has multi-out. */
				tr_PathProcessBranch();
			}else if( tr_PathComIsMultiInput (stCmdCurrTraceInfo.astPathNext) ){
				/* the next path has multi-in-path: confluence path */
				if( tr_PathIsLoopBeginNode( stCmdCurrTraceInfo.astPathNext ) ){
					/* begin of a new loop */
					/* push current loop */
					Tr_RecInfo( stCmdPathInfoAccess.beginNode.get( stCmdCurrTraceInfo.astPathNext ), EVENT_LOOP_PUSH );
					trace_path_log2(" push loop %ld to %ld\n", stCmdCurrTraceInfo.astLoop,stTrLoopStkAccess.getMax()+1 );
					Tr_StkLoopProcess( STACK_PUSH );
					/* initial new loop */
					stCmdCurrTraceInfo.astLoop = stCmdPathInfoAccess.loopInfo.get( stCmdCurrTraceInfo.astPathNext );
					stCmdCurrTraceInfo.astPath = stCmdCurrTraceInfo.astPathNext;
					stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
					stCmdCurrTraceInfo.astLoopExitBottom = stCmdLoopExitAccess.getMax();
					stCmdCurrTraceInfo.astPathStkBottom = stTrPathStkAccess.getMax();
					stCmdLoopInfoAccess.times.set( stCmdCurrTraceInfo.astLoop, 1 );
					stCmdCurrTraceInfo.loopFlg = LOOP_FLG_IN;
				}else if (tr_PathIsAllInputTraced( stCmdCurrTraceInfo.astPathNext )){
					Tr_RecInfo( stCmdPathInfoAccess.beginNode.get( stCmdCurrTraceInfo.astPathNext ),EVENT_CONFLUX_CONTINUE );
					astPathParam = stCmdPathInfoAccess.param.get( stCmdCurrTraceInfo.astPathNext );
					if( astPathParam > 0 ){
						Tr_PathParamOrMergeTo( astPathParam, stCmdCurrTraceInfo.astPathParam );
					}
					trace_path_log2("\tCONTINUE CONFLUX:(%ld->%ld)\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
					/* multi-in-path: all input path were traced. go ahead */
					stCmdCurrTraceInfo.astPath = stCmdCurrTraceInfo.astPathNext;
					stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
				}else{
					/* stop at PATH that has multi-IN-PATH.
					 * For the efficiency of tracing algorithm,
					 *    n*2 but not n^2*/
					trace_path_log2("\tSTOP CONFLUX:(%ld->%ld)\n", stCmdCurrTraceInfo.astPath, stCmdCurrTraceInfo.astPathNext );
					Tr_RecInfo( stCmdPathInfoAccess.beginNode.get( stCmdCurrTraceInfo.astPathNext ), EVENT_CONFLUX_STOP );
					astPathParam = stCmdPathInfoAccess.param.get( stCmdCurrTraceInfo.astPathNext );
					if( astPathParam == 0 ){
						astPathParam = Tr_PathParamCopyNew(stCmdCurrTraceInfo.astPathParam);
						stCmdPathInfoAccess.param.set( stCmdCurrTraceInfo.astPathNext, astPathParam );
					}else{
						Tr_PathParamOrMergeTo( stCmdCurrTraceInfo.astPathParam, astPathParam );
					}
					stCmdCurrTraceInfo.astPath = 0;
					stCmdCurrTraceInfo.astPathNext = 0;
				}
			}else{
				/* single in, single out,  go ahead */
				stCmdCurrTraceInfo.astPath = stCmdCurrTraceInfo.astPathNext;
				stCmdCurrTraceInfo.astPathNext = stCmdPathInfoAccess.pathOut.get( stCmdCurrTraceInfo.astPath );
			}
		}
		CATCH( TRACEEXIT_FATAL );
	}
	if( rc == TRACEEXIT_END ){
		rc = TRACEEXIT_SUCCESS;
	}
	return ( rc );
}
/* whether in a LOOP  now */
BOOL Tr_PathIsInLoop( VOID ){
	AST astLoop;
	if (stCmdCurrTraceInfo.astLoop <= 0 ){
		return FALSE;
	}
	if( stCmdTraceOption.ucDetectOnceLoop ){
		astLoop = stCmdCurrTraceInfo.astLoop;
		while( astLoop ){
			if( stCmdLoopInfoAccess.times.get( astLoop ) > 1 ){
				return TRUE;
			}
			astLoop = stCmdLoopInfoAccess.parent.get( astLoop );
		}
	}
	return TRUE;
}
